perm filename ZAP[206,LSP] blob
sn#485149 filedate 1979-10-25 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00008 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 .REQUIRE "206MAC.PUB[206,LSP]" source_file
C00003 00003 .if false then begin "zap"
C00011 00004 .hd206 FALL 1979
C00012 00005 #.[10] Write a program mapbin that takes three arguments:
C00014 00006 #.[10] Suppose we represent two a dimensional, m by n, array as a list
C00021 00007 #.[20] Suppose a set of cities, represented by the list CITIES,
C00030 00008 #.[5] Give statements expressing the following facts
C00031 ENDMK
C⊗;
.REQUIRE "206MAC.PUB[206,LSP]" source_file;
.
.odd heading(,,{page}) ;
.even heading({page}, , ) ;
.
.LSPFONT
.basicops
.
.allops
.itemmac 1;
.
.PORTION MAINPORTION
.if false then begin "zap"
.hd206 FALL 1979
.PAGE ← 1
.skip
.cb |Midterm Exam 22nd October 1979|
This examination is open book and notes.
When you are asked to write LISP programs you may use external or internal form.
Read each question carefully and be sure you understand what is wanted before you
begin work. You may use any of the programs defined in chapters I and II,
in writing the requested programs.
There is a total of 50 points possible distributed as indicated at
the beginning of each problem.
GOOD LUCK!!
.begin
.indent 0,3
.item ← 0
#.[5] What well known function does the following program compute:
.begin nofill indent 8,8
⊗⊗foo_x ← baz[<x>,qNIL]⊗
⊗⊗baz[u,v] ← qif qn u qthen v qelse ⊗
⊗⊗_________qif qat qa u qthen baz[qd u,qa u_._v] qelse ⊗
⊗⊗_________baz[qda u_._[qaa u_._qd u],v]⊗
.end
#.[10] Write a program ⊗mapbin that takes three arguments:
a binary operation, ⊗F, a starting value ⊗e, and a list ⊗u and
combines the elements of the list together with ⊗e. If the list is
is empty, the result is ⊗e, if it has one element ⊗x1 then the result
is ⊗⊗F[x1,e]⊗, if it is a two element list ⊗⊗<x1,x2>⊗ the result is
⊗⊗F[x1,F[x2,e]]⊗, etc.. Thus
⊗⊗⊗mapbin[$$PLUS$,$$0$,$$(1 2 3 4)$]=$$12$.⊗
#.[10] Suppose we represent two a dimensional ⊗m by ⊗n array as a list
of lists. Each element of the main list corresponds to a row in the array
and will have ⊗n elements (one for each column). The main list will have
⊗m elements, one for each row. Thus the element in the ⊗⊗i⊗th row and
⊗⊗j⊗th column of the array is the ⊗⊗j⊗th element of the ⊗⊗i⊗th list.
The transpose of a two dimensional ⊗m by ⊗n array is an ⊗n by ⊗m array
whose columns are the rows of the original (and whose rows therefore
are the columns of the original).
Write a program ⊗transpose that takes a list representing an array and
returns the list representing its transpose. For example
⊗⊗⊗transpose $$((A B C) (D E F))$=$$((A D) (B E) (C F))$.⊗
Note that the list representing the transpose of an array is the same
as the list representing the array by listing the columns instead of the
rows.
[Turn the page over to find the rest of the exam!]
.next page
#.[20] Suppose a set of cities, represented by the list ⊗CITIES,
are interconnected by railroads. We use the edge representation of graphs from
problem 4 of the homework to represent the shipping needs of these cities.
Thus the edge $$(A B 6)$ indicates that $6 tons of goods must be shipped from
city $A to city $B, i.e. they will be picked up at $A and unloaded at $B.
Call this graph ⊗FREIGHT.
Someone at the railroad chooses a route for the train to follow. This
route is represented by a list of cities in the order they are visited,
e.g. $$(A B C)$. No city is visted more than once.
While travelling this route, the train will pick up all goods which are to be
delivered to any city appearing later in the route.
Write a program ⊗pickup which takes the graph ⊗FREIGHT and a route ⊗ROUTE,
and a city ⊗CITY, appearing in the route, and returns a list of the form
$$((city number) ...)$ which describes how much freight is to be picked up at
⊗CITY and for what destinations. Thus $$(B 4)$ means pick up $4 tons to go to $B.
Write similar program, ⊗drop, which returns a list of the same form,
describing how many tons are to be dropped at ⊗CITY, and where they came from.
The railraod has the problem that the train has a maximum capacity of ⊗FULL tons.
Using ⊗pickup and ⊗drop, write a program ⊗loadcheck that returns $OVERLOAD
if the train will ever have to carry more than ⊗FULL tons as it goes along
⊗ROUTE and returns $OK otherwise.
[Recall that ⊗assoc is useful for manipulating lists of properties such as
the results of ⊗pickup and ⊗drop. ]
#.[5] Give formal statements expressing the following facts
.begin indent 6,6
##. ⊗⊗revers⊗ing a list does not change its ⊗length.
##. ⊗⊗append⊗ing a single element list onto a second list is the same
as ⊗⊗cons⊗ing that element onto the second list.
For example the statement ⊗⊗∀u:_u*qNIL=u⊗ expresses the fact that qNIL is
the right identity for ⊗append, e.g. the result of ⊗⊗append⊗ing
a list onto the empty list is just that list.
.end
.end
.end "zap"
.hd206 FALL 1979
.PAGE ← 1
.skip
.cb |Midterm Exam: Solutions|
.begin
.indent 0,3
.item ← 0
#.[5] What well known function does the following program compute:
.begin nofill indent 8,8
⊗⊗foo_x ← baz[<x>,qNIL]⊗
⊗⊗baz[u,v] ← qif qn u qthen v qelse ⊗
⊗⊗_________qif qat qa u qthen baz[qd u,qa u_._v] qelse ⊗
⊗⊗_________baz[qda u_._[qaa u_._qd u],v]⊗
.end
Solution: ⊗⊗∀x: foo x = fringe x⊗
#.[10] Write a program ⊗mapbin that takes three arguments:
a binary operation, ⊗F, a starting value ⊗e, and a list ⊗u and
combines the elements of the list together with ⊗e. If the list is
is empty, the result is ⊗e, if it has on element ⊗x1 the the result
is ⊗⊗F[x1,e]⊗, if it is a two element list ⊗⊗<x1,x2>⊗ the result is
⊗⊗F[x1,F[x2,e]]⊗, etc.. Thus
⊗⊗⊗mapbin[$$PLUS$,$$0$,$$(1 2 3 4)$]=$$10$.⊗
Solution: ⊗⊗mapbin[F,e,u] ← qif qn u qthen e qelse F[qa u,mapbin[F,e,qd u]]⊗
or in internal form
.begin nofill select 6 indent 8,8
(DEFUN MAPBIN (F E U)
(COND ((NULL U) E)
(T (F (CAR U) (MAPBIN F E (CDR U))))))
.end
#.[10] Suppose we represent two a dimensional, ⊗m by ⊗n, array as a list
of lists. Each element of the main list corresponds to a row in the array
and will have ⊗n elements (one for each column). The main list will have
⊗m elements, one for each row. Thus the element in the ⊗⊗i⊗th row and
⊗⊗j⊗th column of the array is the ⊗⊗j⊗th element of the ⊗⊗i⊗th list.
The transpose of a two dimensional ⊗m by ⊗n array is an ⊗n by ⊗m array
whose columns are the rows of the original (and whose rows therefore
are the columns of the original).
Write a program ⊗transpose that takes a list representing an array and
returns the list representing its transpose. For example
⊗⊗⊗transpose $$((A B C) (D E F))$=$$((A D) (B E) (C F))$.⊗
Note that the list representing the transpose of an array is the same
as the list representing the array by listing the columns instead of the
rows.
Solution: The program ⊗transpose starts by computing the list of
first elements of the rows of the transposed array. These are just
the elements of the first row of the original array, and ⊗mapcar does
the job. It then calls ⊗transp which goes through the remaining rows
of the original array and for each such row adds the elements
to the end of the corresponding new row that is being constructed.
This is done by calling ⊗enquel[u,vl] where ⊗u is the row of the
original array to be processed next and ⊗vl is the new list of rows.
.begin nofill select 2 turnon "∂"
.group
.n←4
∂(n+8)transpose ul ← qif qn ul qthen qNIL qelse transp[qd ul, mapcar[[λx: <x>], qa ul]]
.apart
.group
∂(n+8)transp[ul, vl] ← qif qn ul qthen vl qelse transp[qd ul, enquel[qa ul, vl]]
.apart
.group
∂(n+8)enquel[u, vl] ← qif qn u qthen qNIL qelse [qa vl * <qa u>] . enquel[qd u, qd vl]
.end
or in internal form
.begin nofill select 6 indent 6,6
.group
(DEFUN TRANSPOSE (UL)
(COND ((NULL UL) NIL)
(T (TRANSP (CDR UL)
(MAPCAR (FUNCTION (LAMBDA (X) (LIST X)))
(CAR UL))))))
.apart
.group
(DEFUN TRANSP (UL VL)
(COND ((NULL UL) VL)
(T (TRANSP (CDR UL) (ENQUEL (CAR UL) VL)))))
.apart
.group
(DEFUN ENQUEL (U VL)
(COND ((NULL U) NIL)
(T (CONS (APPEND (CAR VL) (LIST (CAR U)))
(ENQUEL (CDR U) (CDR VL))))))
.end
A somewhat more efficient solution is given by ⊗transpos,trans,stackl. They
work in essentially the same way, but start by reversing the the list
of rows so that the new list of rows can be built by adding to the
fronts of the old rows rather that to the end, thus avoiding excessive use
of ⊗append.
.begin nofill select 2 turnon "∂"
.group
.n←4
∂(n+8)transpos ul ← qif qn ul qthen qNIL qelse [λvl:trans[qd vl,mapcar[[λx:<x>],qa vl]]][reverse ul]
.apart
.group
∂(n+8)trans[ul, vl] ← qif qn ul qthen vl qelse trans[qd ul, stackl[qa ul, vl]]
.apart
.group
∂(n+8)stackl[u, vl] ← qif qn u qthen qNIL qelse [qa u . qa vl] . stackl[qd u, qd vl]
.end
The internal forms of these programs are:
.begin nofill select 6 indent 6,6
.group
(DEFUN TRANSPOS (UL)
(COND ((NULL UL) NIL)
(T ((LAMBDA (VL)
(TRANS (CDR VL)
(MAPCAR (FUNCTION (LAMBDA (X) (LIST X)))
(CAR VL))))
(REVERSE UL)) )))
.apart
.group
(DEFUN TRANS (UL VL)
(COND ((NULL UL) VL)
(T (TRANS (CDR UL) (STACKL (CAR UL) VL)))))
.apart
.group
(DEFUN STACKL (U VL)
(COND ((NULL U) NIL)
(T (CONS (CONS (CAR U) (CAR VL)) (STACKL (CDR U) (CDR VL))))))
.end
A third solution given by many students is:
⊗⊗⊗transpose u←qif [qn u qor qn qa u] qthen qNIL qelse
mapcar[qqa, u]_._transpose mapcar[qqd,u]⊗
which has the internal form
.begin nofill select 6 indent 6,6
.group
(DEFUN TRANSPOSE (U)
(COND ((OR (NULL U) (NULL (CAR U))) NIL)
(T (CONS (MAPCAR (FUNCTION CAR) U)
(TRANSPOSE (MAPCAR (FUNCTION CDR) U))))))
.end
#.[20] Suppose a set of cities, represented by the list ⊗CITIES,
are interconnected by railroads. We use the edge representation of graphs from
problem 4 of the homework to represent the shipping needs of these cities.
Thus the edge $$(A B 6)$ indicates that $6 tons of goods must be shipped from
city $A to city $B, i.e. they will be picked up at $A and unloaded at $B.
Call this graph ⊗FREIGHT.
Someone at the railroad chooses a route for the train to follow. This
route is represented by a list of cities in the order they are visited,
e.g. $$(A B C)$. No city is visted more than once.
While travelling this route, the train will pick up all goods which are to be
delivered to any city appearing later in the route.
Write a program ⊗pickup which takes the graph ⊗FREIGHT and a route ⊗ROUTE,
and a city ⊗CITY, appearing in the route, and returns a list of the form
$$((city number) ...)$ which describes how much freight is to be picked up at
⊗CITY and for what destinations. Thus $$(B 4)$ means pick up $4 tons to go to $B.
Write similar program, ⊗drop, which returns a list of the same form,
describing how many tons are to be dropped at ⊗CITY, and where they came from.
The railraod has the problem that the train has a maximum capacity of ⊗FULL tons.
Using ⊗pickup and ⊗drop, write a program ⊗loadcheck that returns $OVERLOAD
if the train will ever have to carry more than ⊗FULL tons as it goes along
⊗ROUTE and returns $OK otherwise.
Solution:
First of all, it is important to determine which cities precede of follow CITY in
ROUTE. FIND-GOOD-CITIES finds the cities following CITY in ROUTE.
By reversing ROUTE we use it to find the cities preceding to CITY in ROUTE.
We use the cities following CITY in PICKUP, and the cities preceding in
DROP.
Having got these cities, calling the list of them GOOD-CITIES, we now map through FREIGHT, looking for
edges of the correct form, i.e., one city is CITY, the other is in GOOD-CITIES.
(The desired order is opposite in PICKUP and DROP.)
We use MAP-APPEND, which was defined in the
solutions of the first homework; there are a variety of ways to achieve the same effect.
To do LOADCHECK we need to keep track of the load being carried as the train
goes from city to city along route. We use the program LC, which has a variable for this, initialized
to 0. At each city we compute the change in the load by totalling up what
is picked up and dropped. We check the new total against FULL.
.begin nofill select 2 turnoff "{"
.group
.n←8
⊗⊗ pickup[city, route, freight] ← ⊗
⊗⊗ {find-good-cities[city, route]}[λgood-cities: ⊗
⊗⊗ map-append[⊗
⊗⊗ [λx: qif qa x = city ∧ qad x ε good-cities qthen <qd x>], ⊗
⊗⊗ freight]]⊗
.apart
.group
⊗⊗ drop[city, route, freight] ← ⊗
⊗⊗ {find-good-cities[city, reverse route]}[λgood-cities: ⊗
⊗⊗ map-append[⊗
⊗⊗ [λx: qif qad x = city ∧ qa x ε good-cities qthen ⊗
⊗⊗ <<qa x, qadd x>>], ⊗
⊗⊗ freight]]⊗
.apart
.group
⊗⊗ find-good-cities[city, route] ← ⊗
⊗⊗ qif qn route qthen $$ERROR-I-THOUGHT-YOU-SAID-CITY-WAS-IN-ROUTE!$⊗
⊗⊗ qelse qif qa route = city qthen qd route⊗
⊗⊗ qelse find-good-cities[city, qd route]⊗
.apart
.group
⊗⊗ loadcheck[route, freight] ← lc[route, freight, 0]⊗
⊗⊗ lc[route, freight, load] ← ⊗
⊗⊗ qif qn route qthen $$OK$⊗
⊗⊗ qelse apply [⊗
⊗⊗ [λp, d: qif load + p + -d > full qthen $$OVERLOAD$⊗
⊗⊗ qelse lc[qd route, freight, load + p + -d]], ⊗
⊗⊗ total pickup[qa route, route, freight], ⊗
⊗⊗ total drop[qa route, route, freight]]⊗
⊗⊗ total info ← apply[$$PLUS$, mapcar[$$CADR$, info]]⊗
.END
.fill
or in internal form
.begin select 6 nofill indent 2,2
.group
(DEFUN PICKUP (CITY ROUTE FREIGHT)
((LAMBDA (GOOD-CITIES)
(MAP-APPEND
(FUNCTION (LAMBDA (X)
(COND ((AND (EQ (CAR X) CITY)
(MEMBER (CADR X) GOOD-CITIES))
(LIST (CDR X))))))
FREIGHT))
(FIND-GOOD-CITIES CITY ROUTE)))
.apart
.group
(DEFUN DROP (CITY ROUTE FREIGHT)
((LAMBDA (GOOD-CITIES)
(MAP-APPEND
(FUNCTION (LAMBDA (X)
(COND ((AND (EQ (CADR X) CITY)
(MEMBER (CAR X) GOOD-CITIES))
(LIST (LIST (CAR X) (CADDR X)))))))
FREIGHT))
(FIND-GOOD-CITIES CITY (REVERSE ROUTE))))
.apart
.group
(DEFUN FIND-GOOD-CITIES (CITY ROUTE)
(COND ((NULL ROUTE) 'ERROR-I-THOUGHT-YOU-SAID-CITY-WAS-IN-ROUTE!)
((EQ (CAR ROUTE) CITY) (CDR ROUTE))
(T (FIND-GOOD-CITIES CITY (CDR ROUTE)))))
.apart
.group
(DEFUN LOADCHECK (ROUTE FREIGHT)
(LC ROUTE FREIGHT 0))
.apart
.group
(DEFUN LC (ROUTE FREIGHT LOAD)
(COND ((NULL ROUTE) 'OK)
(T ((FUNCTION
(LAMBDA (P D)
(COND ((GREATERP (PLUS LOAD P (MINUS D)) FULL)
'OVERLOAD)
(T (LC (CDR ROUTE)
FREIGHT
(PLUS LOAD P (MINUS D)))))))
(TOTAL (PICKUP (CAR ROUTE) ROUTE FREIGHT))
(TOTAL (DROP (CAR ROUTE) ROUTE FREIGHT))))))
.apart
.group
(DEFUN TOTAL (INFO)
(APPLY 'PLUS (MAPCAR 'CADR INFO)))
.end
#.[5] Give statements expressing the following facts
.begin indent 4,4
##. ⊗⊗revers⊗ing a list does not change its ⊗length.
Solution: ⊗⊗∀u:length reverse u=length u.⊗
##. ⊗⊗append⊗ing a single element list onto a second list is the same
as ⊗⊗cons⊗ing that element onto the second list.
Solution: ⊗⊗∀x v: <x>*v = [x_._v]⊗
Alternate solution: ⊗⊗∀u v: [length u = 1 ⊃ u*v = [qa u_._v] ]⊗
.end
.end